﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RouteMaster
{
    class RouteMatcher
    {

        public bool RMIsPossibleRouteInner(BusStop from, BusStop to, RouteItinerary changes, Dictionary<int, BusRoute> _routes)
        {
            return IsPossibleRouteInner1(from, to, changes, _routes);
        }

        private bool IsPossibleRouteInner1(BusStop from, BusStop to, RouteItinerary changes, Dictionary<int, BusRoute> _routes)
        {
            bool bRet = IsPossibleRoute1(from, to, changes, _routes);

            if (changes.Count <= 1)
            {
                return bRet;
            }

            // We have multiple routes that make up the journey
            // avoid the luton london northampton cambridge harlow dog leg of 4 jouneys 
            // Can we get rid of one of the routes?

            List<BusRoute> full = changes.Select(change => change._busRoute).ToList();

            // suppress one of the routes
            for (int supress = 0; supress < full.Count; supress++)
            {
                 Dictionary<int, BusRoute> _routesTemp = new Dictionary<int, BusRoute>();
              
                for (int y = 0; y < full.Count; y++)
                {
                    if (y == supress)
                        continue;
                    _routesTemp.Add(full[y].ID, full[y]);
                }

                var changesTemp = new RouteItinerary();

                bool testRet = IsPossibleRoute1(from, to, changesTemp, _routesTemp);
                if (testRet)
                {
                    // we found a multiple route - and we got rid of one - we've changed a condition so recurse!

                    changes.Clear();
                    return RMIsPossibleRouteInner(from, to, changes, _routesTemp);
                }
            }

            return bRet;
        }

         private bool IsPossibleRoute1(BusStop from, BusStop to, RouteItinerary changes, Dictionary<int, BusRoute> _routes)
        {
            // see if there's a trivial route

            if (LookForTrivialQuickestRoute(from, to, changes, _routes))
                return true;

            // a multiple hop journey

            var routesUsed = new List<int>();
            var potentialStops = new List<BusStop>();
          
            foreach (var route in _routes.Values)
            {
                if (route.GetOtherStops(from.ID, potentialStops))
                {
                    routesUsed.Add(route.ID);

                    if (IsAnyPossibleRoute(potentialStops, routesUsed, to, changes, _routes))
                    {
                        changes.Add(new RouteLeg(route, from));
                        return true;
                    }
                }
            }
            return false;
        }

         private bool LookForTrivialQuickestRoute(BusStop from, BusStop to, List<RouteLeg> changes, Dictionary<int, BusRoute> _routes)
        {
            var candidates = _routes.Values.Where(r => r.IsAGoodRoute(from.ID, to.ID));

            if (candidates.Count() == 0)
                return false;

            BusRoute brQuickest = candidates.First();

            foreach (var candidate in candidates)
            {
                if (candidate.GetJouneyTime() < brQuickest.GetJouneyTime())
                {
                    brQuickest = candidate;
                }
            }

            changes.Add(new RouteLeg(brQuickest, from));
            return true;
        }

        private bool IsAnyPossibleRoute(IEnumerable<BusStop> potentialStops, List<int> routesUsed, BusStop to,
            RouteItinerary changes, Dictionary<int, BusRoute> _routes)
        {
            foreach (var bs in potentialStops)
            {
                foreach (var r in _routes.Values)
                {
                    if (r.IsAGoodRoute(bs.ID, to.ID))
                    {
                        routesUsed.Add(r.ID);
                        changes.Add(new RouteLeg(r, bs));
                        return true;
                    }
                }
            }

            // a multiple hop journey???

            foreach (var bs in potentialStops)
            {
                foreach (var busRoute in _routes.Values)
                {
                    if (routesUsed.Contains(busRoute.ID))
                        continue;

                    var stepPotentialStops = new List<BusStop>();

                    if (busRoute.GetOtherStops(bs.ID, stepPotentialStops))
                    {
                        routesUsed.Add(busRoute.ID);

                        // recursive call!
                        if (IsAnyPossibleRoute(stepPotentialStops, routesUsed, to, changes, _routes))
                        {
                            changes.Add(new RouteLeg(busRoute, bs));
                        
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }
}
